home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / source / src / dict / _ch_hash.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-11-16  |  4.4 KB  |  251 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  _ch_hash.c
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16. #include <LEDA/impl/ch_hash.h>
  17.  
  18. //------------------------------------------------------------------------------
  19. //
  20. //  hashing with chaining
  21. //
  22. //  S. Naeher (1994)
  23. //
  24. //------------------------------------------------------------------------------
  25.  
  26.  
  27. ch_hash_elem ch_hash::STOP;
  28.  
  29.  
  30. int ch_hash::next_pow(int x) const
  31. { // return next power of 2
  32.   int result = 1;    
  33.   while ((x>>=1) > 0) result <<= 1;
  34.   return result;
  35.  }
  36.  
  37.  
  38. ch_hash_item ch_hash::search(GenPtr x, ch_hash_item& pred) const
  39. { register ch_hash_item p;
  40.  
  41.   STOP.k = x;
  42.  
  43.   if (int_type())
  44.   { p = table + (int(x) & table_size_1);  // table_size = power of 2
  45.     while (p->succ->k != x) p = p->succ;
  46.    }
  47.   else
  48.   { p = table + (hash_fct(x) & table_size_1);
  49.     while (cmp(p->succ->k,x) != 0) p = p->succ;
  50.    }
  51.  
  52.   pred = p;
  53.  
  54.   return p->succ;
  55. }
  56.  
  57.  
  58. ch_hash_item ch_hash::lookup(GenPtr x) const
  59. { register ch_hash_item q;
  60.  
  61.   STOP.k = x;
  62.  
  63.   if (int_type())
  64.   { q = table[int(x) & table_size_1].succ;  // table_size = power of 2
  65.     while (q->k != x) q = q->succ;
  66.    }
  67.   else
  68.   { q = table[hash_fct(x) & table_size_1].succ;
  69.     while (cmp(q->k,x)) q = q->succ;
  70.    }
  71.  
  72.   return (q == &STOP) ? 0 : q;
  73. }
  74.  
  75.  
  76. void ch_hash::change_inf(ch_hash_item p, GenPtr x)
  77. { clear_inf(p->i);
  78.   p->i = x;
  79.   copy_inf(p->i);
  80.  }
  81.  
  82. void ch_hash::del(GenPtr x)
  83. { ch_hash_item p;
  84.   ch_hash_item q = search(x,p);
  85.  
  86.   if (q==&STOP) return;
  87.  
  88.   clear_key(q->k);
  89.   clear_inf(q->i);
  90.  
  91.   p->succ = q->succ;
  92.   delete q;
  93.   count--;
  94.   if (count == low_table) rehash(low_table);
  95.  }
  96.  
  97.  
  98. void ch_hash::del_item(ch_hash_item q)
  99. { register ch_hash_item p = table + (hash_fct(q->k) & table_size_1);
  100.   while(p->succ != q) p = p->succ;
  101.   clear_key(q->k);
  102.   clear_inf(q->i);
  103.   p->succ = q->succ;
  104.   delete q;
  105.   count--;
  106.   if (count == low_table) rehash(low_table);
  107.  }
  108.   
  109.   
  110.   
  111.  
  112. ch_hash_item ch_hash::insert(GenPtr x, GenPtr y)
  113. { ch_hash_item p;
  114.   ch_hash_item q = search(x,p);
  115.  
  116.   if (q != &STOP)
  117.   { clear_inf(q->i);
  118.     q->i = y;
  119.     copy_inf(q->i);
  120.     return q;
  121.    }
  122.  
  123.    copy_key(x);
  124.    copy_inf(y);
  125.  
  126.    q = new ch_hash_elem(x,y,&STOP);
  127.    q->succ = &STOP;
  128.    p->succ = q;
  129.  
  130.    count++;
  131.  
  132.    if (count == high_table) rehash(high_table);
  133.  
  134.    return q;
  135.  
  136. }
  137.  
  138.  
  139.  
  140. void ch_hash::destroy()
  141. { 
  142.   for(int i=0; i < table_size; i++) 
  143.   { ch_hash_item p = table[i].succ;
  144.     ch_hash_item q = p;
  145.     while (p != &STOP)
  146.     { clear_key(p->k);
  147.       clear_inf(p->i);
  148.       q = p;
  149.       p = p->succ;
  150.       delete q;
  151.     }
  152.    }
  153.   //delete[] table;
  154.   free(table);
  155. }
  156.  
  157.  
  158. void ch_hash::init(int T)
  159. { register int i;
  160.  
  161.   table_size   = T;
  162.   table_size_1 = T-1;
  163.  
  164.   low_table  = (table_size > 1024) ? table_size >> 1 : -1;
  165.   high_table = table_size << 1;
  166.  
  167.  
  168.   //table = new ch_hash_elem[table_size];
  169.   table = (ch_hash_elem*)malloc(table_size*sizeof(ch_hash_elem));
  170.  
  171.   for(i=0; i<table_size; i++) table[i].succ = &STOP;
  172.  
  173.   count = 0;
  174. }
  175.  
  176.  
  177. void ch_hash::rehash(int T)
  178. { 
  179.   if (T == table_size) return;
  180.  
  181.   register ch_hash_item p;
  182.   register ch_hash_item q;
  183.   register ch_hash_item r;
  184.  
  185.   ch_hash_item old_table = table;
  186.   int old_table_size = table_size;
  187.   int old_count = count;
  188.  
  189.   init(T);
  190.  
  191.   if (int_type())
  192.    { for (int i=0; i<old_table_size; i++)
  193.      { p = old_table[i].succ;
  194.        while(p != &STOP)
  195.        { r = p->succ;
  196.          q = table + (int(p->k) & table_size_1);
  197.          p->succ = q->succ;
  198.          q->succ = p;
  199.          p = r;
  200.         }
  201.       }
  202.     }
  203.   else
  204.    { for (int i=0; i<old_table_size; i++)
  205.      { p = old_table[i].succ;
  206.        while(p != &STOP)
  207.        { r = p->succ;
  208.          q = table + (hash_fct(p->k) & table_size_1);
  209.          p->succ = q->succ;
  210.          q->succ = p;
  211.          p = r;
  212.         }
  213.       }
  214.     }
  215.  
  216.   count = old_count;
  217.  
  218.   //delete[] old_table;
  219.   free(old_table);
  220. }
  221.  
  222.  
  223. ch_hash::ch_hash(const ch_hash& D)
  224. { ch_hash_item p;
  225.   init(D.table_size);
  226.   for (int i=0; i<table_size; i++)
  227.   { p = D.table[i].succ;
  228.     while(p != &STOP)
  229.     { insert(p->k,p->i);
  230.       D.copy_key(p->k);
  231.       D.copy_inf(p->i);
  232.       p = p->succ;
  233.     }
  234.   }
  235. }
  236.  
  237.  
  238. ch_hash& ch_hash::operator=(const ch_hash& D)
  239. { ch_hash_item p;
  240.   clear();
  241.   for (int i=0; i<D.table_size; i++)
  242.   { p = D.table[i].succ;
  243.     while(p != &STOP)
  244.     { insert(p->k,p->i);
  245.       p = p->succ;
  246.      }
  247.    }
  248.   return *this;
  249. }
  250.  
  251.